#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 679. 24 点游戏.py
@time: 2022/2/20 18:26
@desc: https://leetcode-cn.com/problems/24-game/
> 给定一个长度为4的整数数组cards。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符['+', '-', '*', '/']和括号'('和')'将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
例如，4 /(1 - 2 / 3)= 4 /(1 / 3)= 12。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false。

@解题思路：
    1. 暴力回溯，两两运算
    2. 好难，但字节跟阿里云都考过
    3. Ot(1), Os(1)
'''


class Solution:
    def judgePoint24(self, cards: list) -> bool:
        """
        :type cards: List[int]
        :rtype: bool
        """
        TARGET = 24
        ZERO = 1e-6
        ADD, MUTI, SUB, DIV = 0, 1, 2, 3

        def backtrack(nums):
            # 回溯结束条件
            if not nums: return False
            if len(nums) == 1:
                return abs(nums[0] - TARGET) < ZERO

            # 遍历所有两两组合
            for i, x in enumerate(nums):
                for j, y in enumerate(nums):
                    # 重复则跳过
                    if i == j: continue
                    new_nums = []  # 当前两两组合运算后的结果，其结构为[未参与组合的若干其他卡片，当前组合运算结果]
                    for k, z in enumerate(nums):
                        # 将没参与的数字加入
                        if not k == i and not k == j: new_nums.append(z)

                    for c in range(4):
                        # 剪枝：符合交换律的且当前组合是已经遍历过的相反组合，比如(0, 1)与(0, 1), 则剪枝
                        if c < 2 and i > j: continue
                        if c == ADD:
                            new_nums.append(x + y)
                        elif c == MUTI:
                            new_nums.append(x * y)
                        elif c == SUB:
                            new_nums.append(x - y)
                        else:
                            # 0做除数则跳过
                            if abs(y) < ZERO: continue
                            new_nums.append(x / y)

                        # 继续遍历
                        if backtrack(new_nums): return True
                        # 若跳过上一句，说明当前的(i, j)不符合，弹出该组合，遍历其他组合
                        new_nums.pop()

            return False

        return backtrack(cards)